package com.weave.circle;

/**
 * @Description
 * 循环队列：通过动态数组实现，将复杂度降为O(1)
 * 环形队列也是队列的一种数据结构, 也是在队头出队, 队尾入队;
 * 只是环形队列的大小是确定的, 不能进行一个长度的增加, 当你把一个环形队列创建好之后, 它能存放的元素个数是确定的;
 * 一般我们实现这个环形队列是通过一个连续的结构来实现的;
 * 虽然环形队列在逻辑上是环形的, 但在物理上是一个定长的数组;
 * 那如何在逻辑上形成一个环形的变化, 主要是在头尾指针当走到连续空间的末尾的时候, 它会做一个重置的操作
 * @Author weave
 * @Date 2023/10/17 10:09
 */
public class CircleQueue<E> {
    // 队头元素的索引，不一定就是index=0的位置
    private int front;
    // 当前队列中元素的数量
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    public int size(){
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[index(i)] = null;
        }
        front = 0;
        size = 0;
    }

    /**
     * 入队
     * @param element element
     */
    public void enQueue(E element){
        ensureCapacity(size +1);
        elements[index(size)] = element;
        size++;
    }

    /**
     * 出队
     * @return
     */
    public E deQueue(){
        E frontElement = elements[front];
        elements[front] = null;
        // 将下一个元素指定为队头
        front = index(1);
        size--;
        return frontElement;
    }

    /**
     * 队头元素
     * @return
     */
    public E front(){
        return elements[front];
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("capcacity=").append(elements.length)
                .append(" size=").append(size)
                .append(" front=").append(front)
                .append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(elements[i]);
        }
        string.append("]");
        return string.toString();
    }

    /**
        这个`index`方法的作用是计算环形队列中元素的实际索引。在环形队列中，元素是在一个固定大小的数组中循环存储的。`front`变量表示队列头部元素在数组中的位置，而`size`变量表示队列中元素的数量。
    当你想要访问队列中的一个元素时，你不能直接使用它在队列中的位置（从0开始）作为数组索引，因为队列头部可能不在数组的开始位置。所以，你需要使用`index`方法来计算元素在数组中的实际位置。
    这个方法首先将输入的索引（表示元素在队列中的位置）加上`front`（表示队列头部在数组中的位置），得到一个临时索引。然后，如果这个临时索引大于或等于数组的长度，就从它减去数组的长度，得到最终的数组索引。这样就可以正确地处理环形存储结构中索引超过数组长度的情况。
    总的来说，这个方法就是将队列中的位置转换为数组中的索引，以便正确地访问和操作环形队列中的元素。
        使用的方法是：取余，realIndex = (head + index) %  elements.length；index从0开始
        已知n>=0，m>0 n%m 等价于 n – (m > n ? 0 : m) 的前提条件：n < 2m。取余比单纯的加减法复杂度高
     * @param index 指定的索引，从0开始
     */
    private int index(int index){
        index += front;
        return index - (index >= elements.length? elements.length : 0);
    }

    /**
     * 动态扩容
     * @param capacity
     */
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if(oldCapacity >= capacity){
            return;
        }

        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for(int i=0;i<size;i++){
            newElements[i] = elements[index(i)];
        }
        elements = newElements;

        // 重置front
        front = 0;
    }
}
